package leetcode每日一题;

import javax.swing.tree.TreeNode;
import java.util.*;

/**
 * 1. 问题描述
 *      给定一个二叉树，返回其节点值的锯齿形层序遍历。
 *      （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 *
 * 2. 算法分析
 *      目前只想到一种方式，利用队列数据结构，下面代码有详细注释
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 二叉树的锯齿形层序遍历 {
    /**
     * 节点类
     */
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public static void main(String[] args) {

    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 边界判断
        if(root == null) {
            return new ArrayList<>();
        }
        // 存放最终结果
        List<List<Integer>> ans = new ArrayList<>();
        // 二叉树的层序遍历使用的是BFS：广度优先遍历 采用队列数据结构辅助实现
        Queue<TreeNode> queue = new ArrayDeque<>(); // 创建队列 add  remove
        queue.add(root); // 将root节点入队列
        boolean isReverse = false; // 设置布尔变量，判断当前是否反转,初始为false
        while(!queue.isEmpty()) {
            List<Integer> curList = new ArrayList<>(); // 存放当前层的元素
            Queue<TreeNode> curqueue = new ArrayDeque<>(); // 存放当前层的所有孩子节点
            int[] temp = new int[queue.size()]; // 用数组记录每层元素
            int index = 0; // 索引计数器
            // 取出当前队列中的所有元素
            for(TreeNode node : queue) {
                temp[index] = node.val;
                index++;
                // 当前node的左孩子不空，添加到临时队列中
                if(node.left != null) {
                    curqueue.add(node.left);
                }
                // 当前node的右孩子不空，添加到临时队列中
                if(node.right != null) {
                    curqueue.add(node.right);
                }
            }
            queue = curqueue; // 注意不能直接将上述的node的左右孩子添加到queue中，需要额外开辟一个队列来存放当前层的左右孩子
            // 当前层的元素都添加到curList中
            // 判断当前是否逆序
            if(isReverse) {
                // 如果当前需要逆序
                for(int i = temp.length-1; i >= 0; i--) {
                    curList.add(temp[i]);
                }
                ans.add(curList);
            } else {
                // 如果当前不需要逆序
                for(int i = 0; i < temp.length; i++) {
                    curList.add(temp[i]);
                }
                ans.add(curList);
            }
            isReverse = !isReverse; // 反转（注意第一层不需要反转，然后每层相反，即让isReverse取反即可）
        }
        return ans;
    }

    /**
     * 优化
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>(); // 其底层继承的是Deque
        queue.offer(root); // 将根节点入队
        while(!queue.isEmpty()) {
            int cursize = queue.size(); // 当前队列中的节点数量
            List<Integer> curtemp = new ArrayList<>(); // 存放当前层的节点list
            for(int i = 0; i < cursize; i++) {
                TreeNode node = queue.poll(); // 取出节点
                curtemp.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            ans.add(curtemp);
        }
        return ans;
    }
}
